package com.lw.leetcode.bingChaJi.c;

import com.lw.test.util.Utils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 2157. 字符串分组
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/9 10:06
 */
public class GroupStrings {

    public static void main(String[] args) {
        GroupStrings test = new GroupStrings();

        // [2,3]
//        String[] words = {"a", "b", "ab", "cde"};

        // [1,3]
//        String[] words = {"a", "ab", "abc"};

        // [1,4]
//        String[] words = {"a", "a", "a", "a"};

        // [1,2]
//        String[] words = {"ab", "ba"};

        // [1,2]
//        String[] words = {"ab", "bc", "cd", "de", "f", "ef"};

        //
//        String[] words =Utils.getStrs( Utils.readFileNote("C:\\lw\\123.txt"));
        String[] words = Utils.getStrs(Utils.readFileNote("C:\\lw\\111.txt"));

        int[] ints = test.groupStrings(words);
        System.out.println(Arrays.toString(ints));

    }

    private Map<Integer, Integer> map = new HashMap<>();
    private int[] arr;

    public int[] groupStrings(String[] words) {
        int length = words.length;
        this.arr = new int[length];
        int s = 26;
        int[] flags = new int[s];
        for (int i = 0; i < s; i++) {
            flags[i] = 1 << i;
        }
        for (int i = 0; i < length; i++) {
            arr[i] = i;
            String word = words[i];
            int item = 0;
            for (int j = word.length() - 1; j >= 0; j--) {
                item |= (1 << (word.charAt(j) - 'a'));
            }
            Integer v = map.get(item);
            if (v != null) {
                arr[i] = find(v);
                continue;
            }
            for (int j = 0; j < s; j++) {
                Integer l = map.get(item ^ flags[j]);
                if (l != null) {
                    arr[find(arr[i])] = find(l);
                }
            }
            for (int j = 0; j < s; j++) {
                if ((item | flags[j]) == item) {
                    for (int k = 0; k < s; k++) {
                        if ((item | flags[k]) != item) {
                            Integer l = map.get((item ^ flags[j]) | flags[k]);
                            if (l != null) {
                                arr[find(arr[i])] = find(l);
                            }
                        }
                    }
                }
            }
            map.put(item, i);
        }
        Map<Integer, Integer> counts = new HashMap<>();
        for (int i = 0; i < length; i++) {
            counts.merge(find(arr[i]), 1, (a, b) -> a + b);
        }
        int max = 0;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            max = Math.max(max, entry.getValue());
        }
        return new int[]{counts.size(), max};
    }

    private int find(int t) {
        if (arr[t] == t) {
            return t;
        }
        arr[t] = find(arr[t]);
        return arr[t];
    }

}
